剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/description/?favorite=xb9nqhhg

//排序
int comper(const void*p1,const void*p2)
{
    return *(int*)p1-*(int*)p2;
}

int majorityElement(int* nums, int numsSize)
{
    qsort(nums,numsSize,4,comper);
    return nums[numsSize/2];
}




//摩尔投票法
int majorityElement(int* nums, int numsSize)
{
    int tmp=nums[0];
    int count=1;
    for(int i=1;i<numsSize;i++)
    {
        if(nums[i]==tmp)
        {
            count++;
        }
        else
        {
            count--;
        }

        if(count==0)
        {
            tmp=nums[i+1];
        }
    }
    return tmp;
}